package com.lft.sort12.other_sort;

import java.util.Arrays;

/**
 * PigeonholeSort 鸽巢排序
 */
public class PigeonholeSort {
	public static void main(String[] args) {
		int[] a = {2, 6, 3, -5, 3, 2, 1, 4};
		System.out.println(Arrays.toString(pigeonholeSort(a)));
	}
	
	public static int[] pigeonholeSort(int[] a) {
		// 获取数组中的最大值。
		int max = max(a);
		int min = min(a);
		// 创建桶数组，数组的长度是最大值+1
		int[] buckets = new int[max - min + 1];
		// 循环遍历原数组。以原数组的值为索引，在当前索引的桶内记录个数。
		for (int i = 0; i < a.length; i++) {
			// 以 a[i] - min 的值 为桶的索引，将桶中的计数加1。
			buckets[a[i] - min]++;
		}
		int j = 0;
		// 遍历桶
		for (int i = 0; i <= max - min; i++) {
			// 每个桶中有多少元素
			for (int k = 0; k < buckets[i]; k++) {
				a[j++] = i + min;
			}
		}
		return a;
	}
	
	private static int max(int[] a) {
		int max = a[0];
		for (int i = 0; i < a.length; i++) {
			if (a[i] > max) {
				max = a[i];
			}
		}
		return max;
	}
	
	private static int min(int[] a) {
		int min = a[0];
		for (int i = 0; i < a.length; i++) {
			if (a[i] < min) {
				min = a[i];
			}
		}
		return min;
	}
	
}